package com.iweb;

public class Solution2 {


    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m == 0 & n == 0) return 0.0;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;

        // 小的优化  ： 如果是偶数  y = x
        int x = searchMid(nums1, 0, m - 1, nums2, 0, n - 1, left);
        int y = searchMid(nums1, 0, m - 1, nums2, 0, n - 1, right);

        return (x + y) * 0.5;
    }

    /**
     * @param nums1: 数组1
     * @param s1:    第一个数组的开始位置
     * @param e1:    第一个数组的结束位置
     * @param nums2: 数组2
     * @param s2:    第而个数组的开始位置
     * @param e2:    第二个数组的结束位置
     * @param k:     中位数的位置
     * @return
     */
    public static int searchMid(int[] nums1, int s1, int e1, int[] nums2, int s2, int e2, int k) {
        int len1 = e1 - s1 + 1;
        int len2 = e2 - s2 + 1;
        // 确保长度小的数组在前面
        if (len1 > len2) return searchMid(nums2, s2, e2, nums1, s1, e1, k);
        // 如果其中一个数组被切割完成, 在第二个数组中直接可以找出k位置的数
        if (len1 == 0) return nums2[s2 + k - 1];

        // 如果k==1 说明找到了这个数, 返回小的那个数
        if (k == 1) return Math.min(nums1[s1], nums2[s2]);

        int i = s1 + Math.min(len1, k / 2) - 1; // 需要比较的nums1数组的位置
        int j = s2 + Math.min(len2, k / 2) - 1; // 需要比较的nums2数组的位置

        if (nums1[i] > nums2[j]) {
            return searchMid(nums1, s1, e1, nums2, j + 1, e2, k - (j - s1 + 1));
        } else {
            return searchMid(nums1, i + 1, e1, nums2, s2, e2, k - (i - s1 + 1));
        }
    }

    public static void main(String[] args) {
        int[] a = {2};
        int[] b = {};
        System.out.println(findMedianSortedArrays(a, b));
    }

}
